
//基于排列树实现N皇后
public class QueenTest2 {
    static int N;//皇后数量、行或者列的大小
    static int[] queenLocal;//表示皇后所在的位置，数组下标表示行，数组里面存储的值表示列

    //交换数据的代码
    public static void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    //进行位置是否合法的判断
    public static boolean legal(int row) {
        for (int i = 0; i < row; i++) {
            //第一个条件判断列是不是相同，是不是在不同行，已经选了同一列
            //有两种规律（1）行减行，列减列两值相等；（2）每条对角线行列相减都有各自的定值
            if (queenLocal[i] == queenLocal[row] ||
                    Math.abs(row - i) == Math.abs(queenLocal[row] - queenLocal[i])) {
                return false;
            }
        }
        return true;
    }

    //传入参数是第几行的意思
    //row表示从第几行开始算起；num表示几皇后
    public static void permute(int row, int num) {
        //1.初始化
        N = num;
        queenLocal = new int[N];
        //让皇后们先按对角线排列
        for (int i = 0; i < queenLocal.length; i++) {
            queenLocal[i] = i;
        }
        //2.开始回溯
        dfs(row);
    }

    //满足条件来到output方法，打印皇后们的所在位置
    public static void output() {
        for (int i = 0; i < N; i++) {
            System.out.println("第" + (i + 1) + "个皇后；"
                    + "皇后在第" + i + "行的第" + queenLocal[i] + "列;");
        }
        System.out.println();
    }

    public static void dfs(int row) {
        //证明已经排列到最后一行了
        if (row == N) {
            output();
        } else {
            for (int i = row; i < N; i++) {
                //row表示当前序列的首位元素的下标
                //交换位置，最终达到排列顺序的改变，其实就是不断的改变居于首位的元素
                swap(queenLocal, row, i);
                if (legal(row)) {
                    dfs(row + 1);
                }
                //恢复现场：之前改变了首元素的位置，现在要还原，不然下次再改变首位置元素就会错乱
                swap(queenLocal, row, i);
            }
        }
    }

    public static void main(String[] args) {
        //我这里用八皇后举例，只需要改变传入的num参数，就可以实现不同的皇后效果
        permute(0, 4);
    }
}
